﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using SharpGL;

namespace Graficador3DBinPacking
{
    class AlgoritmoBinPacking
    {
        private int e = 0; //Inicialmente "e" (desperdicio permitido) empieza siendo 0, para ser muy estrictos.
        private int incremento_e ;

        private Timer timer; //Herramienta auxiliar (control-hilo) que usaremos para contabilizar el paso del tiempo.
        private int tiempo = 0; //variable que se irá incrementando con cada segundo transcurrido contabilizado por el timer
        private int TIEMPO_MAX = 1; //tiempo maximo (en segundos) durante el cual se realizara la busqueda de una solucion que cumpla con el criterio del "epsilon"

        private Contenedor C; //este es solo un contenedor de "modelo", para almacenar las dimensiones del contenedor ingresadas por el usuario
        private List<Elemento> L;
        private List<Contenedor> Z = new List<Contenedor>(); //Lista que contiene la solucion final (cada contenedor con sus elementos)
        
        private bool detener = false; //sirve para que cuando el timer llegue al tiempo maximo permitido para realizar la busqueda de una solucion, la busqueda se detenga y el "epsilon" (margen de error permitido) aumente y permita más vacios en el contenedor

        private int desperdicioContenedorActual = 0;
        private int desperdicioTotalContenedores = 0;

        public void BinPacking()
        {
            List<Elemento> S;
            //Objeto3D MinDim;
            List<Objeto3D> listaEspacios;
            
            //C = PedirDatosContenedor(alturaContenedor, longitudContenedor, profundidadContenedor); //pide los datos de un solo contenedor ESTO SI VA
            C = new Contenedor(10, 10, 10, null); //ESTO NO VA PORQUE ES HARDCODE
            listaEspacios = InicializarEspaciosVacios(C);
            incremento_e = HallarIncremento(C._volumen);
            L = InicializarElementos(); //pide los datos de cada elemento (o los lee) y calcula para cada uno su volumen            
            L = OrdenarBurbuja(L); // Según el criterio de volumenes descendente.
            //MinDim = SacarMinimasDimensiones(L);
            InicializaTimer();

            this.timer.Enabled = true; //empieza a correr el tiempo

            while (L.Count!=0) //mientras queden elementos sin haber sido asignados a algún contenedor
            {
                int i = 0; //marca posicion de inicio del primer grupo
                int j = Convert.ToInt32(Math.Ceiling(L.Count / 2.0)); //marca posicion de inicio del segundo grupo, con aproximacion hacia arriba

                S = armaPropuesta(L, i, j, C._volumen, e, listaEspacios); // { Arma una propuesta que cumpla con los requerimientos de "desperdicio máximo admitido para la solución" y de que encaje en las dimensiones del contenedor}
                if (S != null) 
                {
                    //ingreso toda la propuesta (combinacion de elementos) en el contenedor
                    Contenedor C_Sol = new Contenedor(C._ancho, C._alto, C._profundidad, S); //aca le estoy agregando al contenedor toda la solucion completa
                    C_Sol._desperdicio = this.desperdicioContenedorActual; //guardo como atributo del contenedor su desperdicio final (despues de haber introducido los elementos)
                    this.desperdicioTotalContenedores += this.desperdicioContenedorActual; //incremento el desperdicio global (total) de los contenedores
                    this.Z.Add(C_Sol); //se añade el contenedor con sus elementos a la lista "solucion" (lista de contenedores llenos)
                    listaEspacios = InicializarEspaciosVacios(C);  //reinicio los espacios vacios disponibles, esto se usará para el siguiente contenedor
                    timer.Start();
                }
                else 
                {
                    //si S fue null es porque el tiempo para realizar la búsqueda se venció, así que ahora se 
                    //debe incrementar el "e" para realizar más búsquedas
                    listaEspacios = InicializarEspaciosVacios(C); 
                    if (this.e + incremento_e >= C._volumen) {
                        this.e = C._volumen;
                        this.timer.Stop(); //como ya no se puede seguir incrementando el epsilon, permitiré que empiece a rellenar los elementos en los contenedores sin limite de tiempo
                    }
                    else
                    {
                        e = e + incremento_e;
                    }
                            //en esta parte, opcionalmente se PODRIA cambiar el intervalo del timer, para que inicie muy grande y
                            //con cada cambio de e se vaya haciendo más pequeño hasta cierto límite. Porque se asume que AL INICIO las busquedas tardan mas, porque hay más elementos no asignados a los contenedores.
                            //Eso iría aquí (el cambio del intervalo)
                    timer.Start(); //Como el epsilon acaba de incrementar, reiniciamos el contador de tiempo
                }
            }
        }

        public List<Elemento> armaPropuesta(List<Elemento> L, int i, int j, int volumen, int e, List<Objeto3D> listaEspacios)
        { 
            List<Elemento> S = new List<Elemento>();
            int desperdicioActual = volumen;
            bool tieneSolucionCompleta = false;
            Random rng = new Random();
            int num_azar = 0;

            while (!tieneSolucionCompleta && this.detener == false) // Mientras el desperdicio actual sea menor al permitido por el epsilon actual
            {
                while (i < j && this.detener == false)
                {
                    if (i == 1) //agrega un componente aleatorio para generar rutas más variadas que exploten la búsqueda de soluciones que cumplan con lo permitido por el epsilon actual
                    {
                        num_azar = rng.Next(1, L.Count); //un numero entre [1, L.count[                       

                        if (num_azar < L.Count && L[num_azar]._asignado == false && L[num_azar]._volumen <= desperdicioActual && entro(L[num_azar], listaEspacios)) //{Si el elemento no ha sido asignado a algun contenedor anteriormente y ademas el elemento sí entra en el contenedor actual (incluso considerando los objetos que ya están dentro) }
                        {
                            desperdicioActual = desperdicioActual - L[num_azar]._volumen;
                            S.Add(L[num_azar]);
                            if (desperdicioActual <= e) { tieneSolucionCompleta = true; break; }
                        }
                    }
                    if (L[i]._asignado == false && L[i]._volumen <= desperdicioActual && entro(L[i], listaEspacios)) //{Si el elemento no ha sido asignado a algun contenedor anteriormente y ademas el elemento sí entra en el contenedor actual (incluso considerando los objetos que ya están dentro) }
                    {
                        desperdicioActual = desperdicioActual - L[i]._volumen;
                        S.Add(L[i]);
                        if (desperdicioActual <= e) { tieneSolucionCompleta = true; break; }
                    }
                    i++;
                }
                while (j < L.Count && this.detener == false) // "< a L.count? o <= a L.count"
                {
                    if (L[j]._asignado == false && L[j]._volumen <= desperdicioActual && entro(L[j], listaEspacios)) //{Si el elemento no ha sido asignado a algun contenedor anteriormente y ademas el elemento sí entra en el contenedor actual (incluso considerando los objetos que ya están dentro) }
                    {
                        desperdicioActual = desperdicioActual - L[j]._volumen;
                        S.Add(L[j]);
                        if (desperdicioActual <= e) { tieneSolucionCompleta = true; break;  }
                    }
                    j++;
                }
                break;
            }
            if (tieneSolucionCompleta == true)
            {
                foreach (Elemento elemento in S)
                {
                    L.Remove(elemento);
                }
                this.desperdicioContenedorActual = desperdicioActual;
                return S;
            }
            else 
            {
                this.timer.Enabled = false;
                this.detener = false;
                foreach (Elemento elemento in S)
                {
                    elemento._asignado = false; //los desmarco porque en realidad no los agregare al contenedor porque no cumplieron el criterio del epsilon
                }
                return null;
            }
        }

        public List<Elemento> OrdenarBurbuja(List<Elemento> L) //Descendente 
        {
            Elemento temp;
            for (int pasadas = 1; pasadas < L.Count; pasadas++) // pasadas
                for (int i = 0; i < L.Count - 1; i++)
                    if (L[i]._volumen < L[i + 1]._volumen)      // comparar
                    {
                        // intercambiar
                        temp = L[i];
                        L[i] = L[i + 1];
                        L[i + 1] = temp;
                    }
            return L;
        }


        public List<Elemento> InicializarElementos()
        {
            //bool termino = false;
            List<Elemento> L = new List<Elemento>();
            //Elemento p;
            //int ancho, alto, profundidad;
            //PRUEBA 1
            //L.Add(new Elemento(2, 2, 3));
            //L.Add(new Elemento(4, 4, 2));
            //L.Add(new Elemento(5, 2, 1));
            //L.Add(new Elemento(4, 4, 4));
            //L.Add(new Elemento(8, 8, 5));
            //PRUEBA2
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //PRUEBA3
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(2, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //L.Add(new Elemento(7, 10, 10));
            //PRUEBA4
            //L.Add(new Elemento(5, 10, 10));
            //L.Add(new Elemento(2, 4, 10));
            //L.Add(new Elemento(3, 4, 10));
            //L.Add(new Elemento(3, 3, 10));
            //L.Add(new Elemento(2, 6, 10));
            //L.Add(new Elemento(3, 3, 10));
            //PRUEBA5
            L.Add(new Elemento(5, 10, 10));
            L.Add(new Elemento(5, 5, 10));
            L.Add(new Elemento(5, 5, 10));
            L.Add(new Elemento(5, 8, 10));
            return L;
        }

        public int HallarIncremento(int volumen)
        {
            double PORCENTAJE = 5;
            double resultado = (PORCENTAJE / 100.0) * volumen;
            return Convert.ToInt32(resultado);
        }


        public bool entro(Elemento elemento, List<Objeto3D> listaEspacios)
        {
            bool asignadoAespacio = false;
            int i = 0;

            do
            {
                //se comprueba si el objeto entra en el espacio vacío seleccionado
                if (elemento._alto <= listaEspacios[i]._alto &&
                    elemento._ancho <= listaEspacios[i]._ancho &&
                    elemento._profundidad <= listaEspacios[i]._profundidad)
                {
                    //se copia la posicion de inicio del espacio vacio al elemento y se marca
                    //como asignado
                    elemento._x = listaEspacios[i]._x;
                    elemento._y = listaEspacios[i]._y;
                    elemento._z = listaEspacios[i]._z;
                    elemento._asignado = true;
                    asignadoAespacio = true;
                    listaEspacios = GenerarNuevosEspaciosVacios(this.C, listaEspacios, listaEspacios[i], elemento);
                    return asignadoAespacio;
                    //aca podria ir un break, pero se supone que el while (!asignadoAespacio) lo va a sacar del bucle
                }                
                i++;
                
            }
            while (i < listaEspacios.Count); //NO ESTOY SEGURA SI ES i >= o es solo i>
            
            //EliminaEspaciosVaciosInutiles();

            //foreach (espacio_vacio in listaEspaciosVacios)
            //{
                
            //}
            return asignadoAespacio;
        }
        public List<Objeto3D> InicializarEspaciosVacios(Contenedor C)
        { 
            List<Objeto3D> ListaEspacios = new List<Objeto3D>();
            Objeto3D espacio;
            
            espacio = new Objeto3D();
            espacio._alto = C._alto;
            espacio._ancho = C._ancho;
            espacio._profundidad = C._profundidad;
            espacio._volumen = C._volumen;
            espacio._x = espacio._y = espacio._z = 0;
            ListaEspacios.Add(espacio);

            return ListaEspacios;
        }
        public List<Objeto3D> GenerarNuevosEspaciosVacios(Contenedor C, List<Objeto3D> listaEspacios, Objeto3D espacioAdividir, Elemento elemento)
        {
            //el ingreso de un nuevo elemento en un espacio vacio genera como mínimo 3 nuevos espacios vacíos nuevos que cubren el espacio vacio anterior
            Objeto3D sp1 = new Objeto3D();
            Objeto3D sp2 = new Objeto3D();
            Objeto3D sp3 = new Objeto3D();

            sp1._ancho = espacioAdividir._ancho;
            sp1._alto = espacioAdividir._alto;
            sp1._profundidad = espacioAdividir._profundidad - elemento._profundidad;
            sp1._y = espacioAdividir._y;
            sp1._z = espacioAdividir._z;
            sp1._x = elemento._x + elemento._profundidad;

            sp2._ancho = espacioAdividir._ancho;
            sp2._alto = espacioAdividir._alto - elemento._alto;
            sp2._profundidad = elemento._profundidad;
            sp2._x = espacioAdividir._x;
            sp2._z = elemento._z + elemento._alto;
            sp2._y = elemento._y;

            sp3._ancho = espacioAdividir._ancho - elemento._ancho;
            sp3._alto = elemento._alto;
            sp3._profundidad = elemento._profundidad;
            sp3._y = elemento._y + elemento._ancho;
            sp3._x = elemento._x;
            sp3._z = elemento._z;

            listaEspacios.Remove(espacioAdividir);
            listaEspacios.Add(sp1);
            listaEspacios.Add(sp2);
            listaEspacios.Add(sp3);

            return listaEspacios;
        }

        //public Objeto3D SacarMinimasDimensiones( List<Elemento> L)
        //{
        //    Objeto3D MinDim = new Objeto3D();
        //    MinDim._ancho = L[0]._ancho;
        //    MinDim._alto = L[0]._alto;
        //    MinDim._profundidad = L[0]._profundidad;

        //    foreach (Elemento elemento in L)
        //    {
        //        if (elemento._alto < MinDim._alto)
        //        {
        //            MinDim._alto = elemento._alto;
        //        }
        //        if (elemento._ancho < MinDim._ancho)
        //        {
        //            MinDim._ancho = elemento._ancho;
        //        }
        //        if (elemento._profundidad < MinDim._profundidad)
        //        {
        //            MinDim._profundidad = elemento._profundidad;
        //        }
        //    }
        //    return MinDim;
        //}

       
        //public List<Objeto3D> EliminaEspaciosVaciosInutiles(List<Objeto3D> ListaEspacios, Objeto3D MinDim)
        //{
        //    foreach (Objeto3D espacioVacio in ListaEspacios)
        //    {
        //        if (espacioVacio._alto < MinDim._alto || espacioVacio._ancho < MinDim._ancho || espacioVacio._profundidad < MinDim._profundidad)
        //        {
        //            ListaEspacios.Remove(espacioVacio);
        //        }
        //    }
        //    return ListaEspacios;
        //}


        public void InicializaTimer()
        {
            this.timer = new Timer();
            this.timer.Interval = 1000; //para definir que un tick del timer se dará cada 1000 milisegundos (1 segundo)
            this.timer.Enabled = false; //aún no empieza a correr el tiempo
            this.timer.Tick += new EventHandler(Timer_Tick);
        }
        private void Timer_Tick(Object myObject, EventArgs myEventArgs)
        {
            tiempo++;
            //this.txtTiempo.Text = tiempo.ToString();
            if (tiempo >= this.TIEMPO_MAX)
            {
                this.detener = true;
                this.timer.Stop();
                tiempo = 0;
            }
        }

        public Contenedor PedirDatosContenedor(int alturaContenedor, int longitudContenedor, int profundidadContenedor)
        {   
            Contenedor C = new Contenedor(alturaContenedor, longitudContenedor, profundidadContenedor, null);

            return C;
        }

        public int MostrarSolucion(Contenedor [] arregloContenedores)
        {

            int i = 0;
            foreach (Contenedor contenedor in Z)
            {
                arregloContenedores[i] = contenedor;
                i++;
            }
            return i;
            
        }

    }
}
